{"problem":{"name":"[AMPPZ2013] Bytehattan","description":{"content":"比特哈顿镇有 $n\\times n$ 个格点，形成了一个网格图。一开始整张图是完整的。 有 $k$ 次操作，每次会删掉图中的一条边 $(u,v)$，你需要回答在删除这条边之后 $u$ 和 $v$ 是否仍然连通。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10665"},"statements":[{"statement_type":"Markdown","content":"比特哈顿镇有 $n\\times n$ 个格点，形成了一个网格图。一开始整张图是完整的。\n\n有 $k$ 次操作，每次会删掉图中的一条边 $(u,v)$，你需要回答在删除这条边之后 $u$ 和 $v$ 是否仍然连通。\n\n## Input\n\n第一行包含两个正整数 $n,k(2\\leq n\\leq 1500,1\\leq k\\leq 2n(n-1))$，表示网格图的大小以及操作的个数。\n\n接下来 $k$ 行，每行包含两条信息，每条信息包含两个正整数 $a,b(1\\leq a,b\\leq n)$ 以及一个字符 $c$（$c$ 为 `N` 或者 `E`）。\n\n如果 $c$ 为 `N`，表示删除 $(a,b)$ 到 $(a,b+1)$ 这条边；如果 $c$ 为 `E`，表示删除 $(a,b)$ 到 $(a+1,b)$ 这条边。\n\n数据进行了加密，对于每个操作，如果上一个询问回答为 TAK 或者这是第一个操作，那么只考虑第一条信息，否则只考虑第二条信息。数据保证每条边最多被删除一次。\n\n## Output\n\n输出 $k$ 行，对于每个询问，如果仍然连通，输出 TAK，否则输出 NIE。\n\n[samples]\n\n## Note\n\n数据保证，$2\\leq n\\leq 1500$，$1\\leq k\\leq 2n(n-1)$，$1\\leq a,b\\leq n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10665","tags":["图论","2013","并查集","O2优化","ICPC"],"sample_group":[["3 4\n2 1 E 1 2 N\n2 1 N 1 1 N\n3 1 N 2 1 N\n2 2 N 1 1 N","TAK\nTAK\nNIE\nNIE"]],"created_at":"2026-03-03 11:09:25"}}