{"problem":{"name":"[EGOI 2023] Sopsug / 垃圾处理","description":{"content":"砾石堆是隆德郊区的一处未建成的居民区。目前，所有必要的基础设施正在建设中，包括其中最重要的：垃圾处理。与瑞典许多地区一样，将使用一个自动真空收集系统收集垃圾。其原理是使用气压将垃圾通过管道在地下运输。 砾石堆中有 $N$ 座建筑，编号从 $0$ 到 $N-1$。你的任务是用管道连接几对建筑。如果你在建筑 $u$ 和 $v$ 之间连接一条管道，$u$ 将会把所有垃圾运送到 $v$（但不能反向运输）","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9469"},"statements":[{"statement_type":"Markdown","content":"砾石堆是隆德郊区的一处未建成的居民区。目前，所有必要的基础设施正在建设中，包括其中最重要的：垃圾处理。与瑞典许多地区一样，将使用一个自动真空收集系统收集垃圾。其原理是使用气压将垃圾通过管道在地下运输。\n\n砾石堆中有 $N$ 座建筑，编号从 $0$ 到 $N-1$。你的任务是用管道连接几对建筑。如果你在建筑 $u$ 和 $v$ 之间连接一条管道，$u$ 将会把所有垃圾运送到 $v$（但不能反向运输）。你的目标是建立一个由 $N-1$ 个管道组成的网络，使得所有垃圾最终都进入一座建筑。换句话说，你希望整个网络构成一棵有根树，所有边都指向树根。\n\n然而，建筑物间已经建设了 $M$ 条管道。这些管道必须被包含在你的网络中。这些管道是有方向的，只能向一个方向运输。\n\n此外，有 $K$ 对建筑物间无法建设管道。这些建筑物对是有序的，因此如果无法从 $u$ 到 $v$ 建设管道，也有可能从 $v$ 到 $u$ 可以建设管道。\n\n## Input\n\n第一行三个整数 $N,M,K$。\n\n接下来 $M$ 行，每行两个不相等的整数 $a_i,b_i$，表示已经存在一条从 $a_i$ 到 $b_i$ 的管道。\n\n接下来 $K$ 行，每行两个不相等的整数 $c_i,d_i$，表示无法从 $c_i$ 到 $d_i$ 建设管道。\n\n所有 $M+K$ 对有序数对是互不相同的。注意 $(u,v)$ 和 $(v,u)$ 是不同的两对数。\n\n## Output\n\n如果无解，输出 `NO`。\n\n否则，输出 $N-1$ 行，每行两个整数 $u_i,v_i$，表示有一条从 $u_i$ 到 $v_i$ 的管道。你可以以任意顺序输出这些管道。如果有多解，你可以输出任意一个。请记住所有 $M$ 条已经存在的管道必须包含在答案中。\n\n[samples]\n\n## Background\n\nDay 2 Problem C.\n\n题面译自 [EGOI2023 sopsug](https://egoi23.se/assets/tasks/day2/sopsug.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)\n\n## Note\n\n**样例 $1,2$ 解释**\n\n下图展示了前两组样例。蓝色边表示已经存在的管道，红色虚线边表示无法建造的管道。\n\n左图展示了样例 $1$ 和样例输出的方案，黑色边表示新建造的管道。在这个网络中，所有垃圾将被收集在建筑 $0$。这不是唯一解；例如，从 $1$ 到 $3$ 的管道可以被从 $0$ 到 $1$ 的管道代替，此时依然是合法解。\n\n对于样例 $2$，根据右图可以发现，由于环 $(2,3,4)$ 的存在，问题无解。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/n0z2x9vy.png)\n\n---\n\n**数据范围**\n\n对于全部数据，$2\\le N\\le 3\\times 10^5$，$0\\le M\\le 3\\times 10^5$，$0\\le K\\le 3\\times 10^5$，$0\\le a_i,b_i\\le N-1$，$0\\le c_i,d_i\\le N-1$。\n\n- 子任务一（$12$ 分）：$M=0$，$K=1$。\n- 子任务二（$10$ 分）：$M=0$，$K=2$。\n- 子任务三（$19$ 分）：$K=0$。\n- 子任务四（$13$ 分）：$N\\le 100$。\n- 子任务五（$17$ 分）：保证存在解法使得 $0$ 为根。\n- 子任务六（$11$ 分）：$M=0$。\n- 子任务七（$18$ 分）：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9469","tags":["2023","Special Judge","O2优化","EGOI（欧洲/女生）"],"sample_group":[["5 1 8\n4 1\n3 1\n3 4\n3 2\n0 2\n0 4\n2 4\n1 0\n2 0","4 1\n3 0\n1 3\n2 3"],["5 4 0\n1 0\n2 3\n3 4\n4 2\n","NO"],["3 0 1\n0 1","1 0\n2 0"],["4 0 2\n0 1\n1 0","2 0\n3 0\n1 3"]],"created_at":"2026-03-03 11:09:25"}}