{"problem":{"name":"1 or 2","description":{"content":"There are $N$ cards placed face down in a row. On each card, an integer $1$ or $2$ is written. Let $A_i$ be the integer written on the $i$\\-th card. Your objective is to guess $A_1, A_2, ..., A_N$ cor","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc126_e"},"statements":[{"statement_type":"Markdown","content":"There are $N$ cards placed face down in a row. On each card, an integer $1$ or $2$ is written.\nLet $A_i$ be the integer written on the $i$\\-th card.\nYour objective is to guess $A_1, A_2, ..., A_N$ correctly.\nYou know the following facts:\n\n*   For each $i = 1, 2, ..., M$, the value $A_{X_i} + A_{Y_i} + Z_i$ is an even number.\n\nYou are a magician and can use the following magic any number of times:\n**Magic**: Choose one card and know the integer $A_i$ written on it. The cost of using this magic is $1$.\nWhat is the minimum cost required to determine all of $A_1, A_2, ..., A_N$?\nIt is guaranteed that there is no contradiction in given input.\n\n## Constraints\n\n*   All values in input are integers.\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq X_i < Y_i \\leq N$\n*   $1 \\leq Z_i \\leq 100$\n*   The pairs $(X_i, Y_i)$ are distinct.\n*   There is no contradiction in input. (That is, there exist integers $A_1, A_2, ..., A_N$ that satisfy the conditions.)\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$X_1$ $Y_1$ $Z_1$\n$X_2$ $Y_2$ $Z_2$\n$\\vdots$\n$X_M$ $Y_M$ $Z_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc126_e","tags":[],"sample_group":[["3 1\n1 2 1","2\n\nYou can determine all of $A_1, A_2, A_3$ by using the magic for the first and third cards."],["6 5\n1 2 1\n2 3 2\n1 3 3\n4 5 4\n5 6 5","2"],["100000 1\n1 100000 100","99999"]],"created_at":"2026-03-03 11:01:14"}}