{"raw_statement":[{"iden":"problem statement","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?"},{"iden":"constraints","content":"*   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)$"},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"4 4 1\n2 1\n1 3\n3 2\n3 4\n4 1"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"5 10 0\n1 2\n1 3\n1 4\n1 5\n3 2\n2 4\n2 5\n4 3\n5 3\n4 5"},{"iden":"sample output 2","content":"0 0 0 0 0\n\nEveryone is a friend of everyone else and has no friend candidate."},{"iden":"sample input 3","content":"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"},{"iden":"sample output 3","content":"1 3 5 4 3 3 3 3 1 0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}