问题描述

一个平衡网络是一个抽象设备，由 $N$ 条线组成，从左到右排列，以及 $M$ 个将两条线连接起来的平衡器组成。这些线按照从上到下的顺序标记为 $1$ 到 $N$，平衡器按照从左到右的顺序标记为 $1$ 到 $M$。第 $i$ 个平衡器连接着线 $x_i$ 和 $y_i$ ($x_i < y_i$)。

每个平衡器有两种状态：上升或下降。

考虑一个令牌，它从所有平衡器的左侧某条线上开始向右移动。在整个过程中，令牌会且仅会通过每个平衡器一次。每当令牌遇到第 $i$ 个平衡器时，将出现以下情况：

• 如果令牌沿着线 $x_i$ 移动，并且第 $i$ 个平衡器处于下降状态，则令牌向下移动到线 $y_i$ 并继续向右移动。
• 如果令牌沿着线 $y_i$ 移动，并且第 $i$ 个平衡器处于上升状态，则令牌向上移动到线 $x_i$ 并继续向右移动。
• 否则，令牌不会改变其移动的线。

一个平衡网络的状态是一个长度为 $M$ 的字符串，描述了所有平衡器的状态。第 $i$ 个字符为 ^ 表示第 $i$ 个平衡器在上升状态，为 v 表示第 $i$ 个平衡器在下降状态。

如果存在一种状态使得对于任何起始线路 $w$，令牌总是最终停在线 $w$ 上并继续无限地沿着该线运行，则称该平衡网络的状态为统一状态。其他任何状态均称为非统一状态。

给定一个整数 $T$ ($1 \le T \le 2$)，回答以下问题：

• 如果 $T = 1$，找到任意一种统一状态的网络，或判断该状态不存在。
• 如果 $T = 2$，找到任意一种非统一状态的网络，或判断该状态不存在。

请注意，如果您只能正确回答其中一类问题，您可以获得部分分数。

约束条件

• $2 \leq N \leq 50000$
• $1 \leq M \leq 100000$
• $1 \leq T \leq 2$
• $1 \leq x_i < y_i \leq N$
• 所有输入值均为整数。

部分得分

• 对于满足 $T = 1$ 的测试集，将获得 $800$ 分。
• 对于满足 $T = 2$ 的测试集，将获得 $800$ 分。

---

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $T$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_M$ $y_M$

输出

如果 $T = 1$，输出给定网络的任意一种统一状态；如果 $T = 2$，输出给定网络的任意一种非统一状态。如果所需的状态不存在，则输出 -1。

---

示例输入 1

4 5 1
1 3
2 4
1 2
3 4
2 3

示例输出 1

^^^^^

这是一个统一状态：无论从哪个起始线路开始，令牌最终都会停在线 $1$ 上。

---

示例输入 2

4 5 2
1 3
2 4
1 2
3 4
2 3

示例输出 2

v^^^^

这是一个非统一状态：根据起始线路的不同，令牌可能停在线 $1$ 或线 $2$ 上。

---

示例输入 3

3 1 1
1 2

示例输出 3

-1

不存在统一状态。

---

示例输入 4

2 1 2
1 2

示例输出 4

-1

不存在非统一状态。