AT_agc041_e [AGC041E] Balancing Network

平衡网络是一个由 $M$ 个平衡器所连接的 $N$ 根导线所构成的抽象网络系统。这一系统按由左至右的顺序运行。导线从上到下按 $1$ 至 $N$ 编号，平衡器从左到右按 $1$ 至 $M$ 编号。第 $i$ 个平衡器连接着导线 $x_i$ 与 $y_i$。下图是一个平衡网络的示例：  每个平衡器都一定处于以下两种状态之一：向上或向下。 让我们考虑一个令牌，这个令牌在所有平衡器左侧的某个点开始沿某根导线向右移动。在此过程中，每个平衡器都会被令牌恰好**途经**一次。当令牌途经一个平衡器 $i$ 时，可能会发生以下情况： - 如果令牌沿导线 $x_i$ 移动且平衡器 $i$ 处于向下的状态，则令牌会向下移至 $y_i$ 并继续向右移动。 - 如果令牌沿导线 $y_i$ 移动且平衡器 $i$ 处于向上的状态，则令牌会向上移至 $x_i$ 并继续向右移动。 - 否则，令牌不会改变其移动的导线。 我们将所有平衡器的状态用长度为 $M$ 的字符串表示。若第 $i$ 个平衡器处于向上的状态，则第 $i$ 个字符为'`^`'；若第 $i$ 个平衡器处于向下的状态，则第 $i$ 个字符为'`v`'。 如果存在一根导线 $w$ ，使得令牌无论从整个网络的哪一根导线开始移动都能抵达导线 $w$ 且一直沿此导线移动至趋向无穷远的位置，那么这个网络称之为均匀状态；任何的其他状态称之为非均匀状态。 给出一个整数 $T (1 \le T \le 2)$ ，请您根据 $T$ 的值回答以下问题： - 若 $T=1$，则通过自行规定平衡器的方向以构造给出网络的任何均匀状态，或是回答不存在。 - 若 $T=2$，则通过自行规定平衡器的方向以构造给出网络的任何非均匀状态，或是回答不存在。 请注意，若您仅正确回答了一种问题，则您将获得一定的部分分。

无

无

- $2 \le N \le 50000$ - $1 \le M \le 10^5$ - $1 \le T \le 2$ - $1 \le x_i \lt y_i \le N $ - 保证所有输入均为整数。 ### 子任务 - 若您通过了所有 $T=1$ 时的所有测试点，则您将获得 $50 \%$ 的分数。（译注：原文是800分，但本题的实际分数为1600分，翻译时按照 $50 \%$ 翻译） - 若您通过了所有 $T=2$ 时的所有测试点，则您将获得 $50 \%$ 的分数。