{"problem":{"name":"Friend Suggestions","description":{"content":"An SNS has $N$ users - User $1$, User $2$, $\\cdots$, User $N$. Between these $N$ users, there are some relationships - $M$ _friendships_ and $K$ _blockships_. For each $i = 1, 2, \\cdots, M$, there is ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc157_d"},"statements":[{"statement_type":"Markdown","content":"An SNS has $N$ users - User $1$, User $2$, $\\cdots$, User $N$.\nBetween these $N$ users, there are some relationships - $M$ _friendships_ and $K$ _blockships_.\nFor each $i = 1, 2, \\cdots, M$, there is a bidirectional friendship between User $A_i$ and User $B_i$.\nFor each $i = 1, 2, \\cdots, K$, there is a bidirectional blockship between User $C_i$ and User $D_i$.\nWe define User $a$ to be a _friend candidate_ for User $b$ when all of the following four conditions are satisfied:\n\n*   $a \\neq b$.\n*   There is not a friendship between User $a$ and User $b$.\n*   There is not a blockship between User $a$ and User $b$.\n*   There exists a sequence $c_0, c_1, c_2, \\cdots, c_L$ consisting of integers between $1$ and $N$ (inclusive) such that $c_0 = a$, $c_L = b$, and there is a friendship between User $c_i$ and $c_{i+1}$ for each $i = 0, 1, \\cdots, L - 1$.\n\nFor each user $i = 1, 2, ... N$, how many friend candidates does it have?\n\n## Constraints\n\n*   All values in input are integers.\n*   $2 ≤ N ≤ 10^5$\n*   $0 \\leq M \\leq 10^5$\n*   $0 \\leq K \\leq 10^5$\n*   $1 \\leq A_i, B_i \\leq N$\n*   $A_i \\neq B_i$\n*   $1 \\leq C_i, D_i \\leq N$\n*   $C_i \\neq D_i$\n*   $(A_i, B_i) \\neq (A_j, B_j) (i \\neq j)$\n*   $(A_i, B_i) \\neq (B_j, A_j)$\n*   $(C_i, D_i) \\neq (C_j, D_j) (i \\neq j)$\n*   $(C_i, D_i) \\neq (D_j, C_j)$\n*   $(A_i, B_i) \\neq (C_j, D_j)$\n*   $(A_i, B_i) \\neq (D_j, C_j)$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$A_1$ $B_1$\n$\\vdots$\n$A_M$ $B_M$\n$C_1$ $D_1$\n$\\vdots$\n$C_K$ $D_K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc157_d","tags":[],"sample_group":[["4 4 1\n2 1\n1 3\n3 2\n3 4\n4 1","0 1 0 1\n\nThere is a friendship between User $2$ and $3$, and between $3$ and $4$. Also, there is no friendship or blockship between User $2$ and $4$. Thus, User $4$ is a friend candidate for User $2$.\nHowever, neither User $1$ or $3$ is a friend candidate for User $2$, so User $2$ has one friend candidate."],["5 10 0\n1 2\n1 3\n1 4\n1 5\n3 2\n2 4\n2 5\n4 3\n5 3\n4 5","0 0 0 0 0\n\nEveryone is a friend of everyone else and has no friend candidate."],["10 9 3\n10 1\n6 7\n8 2\n2 5\n8 4\n7 3\n10 9\n6 4\n5 8\n2 6\n7 5\n3 1","1 3 5 4 3 3 3 3 1 0"]],"created_at":"2026-03-03 11:01:14"}}