No.2301 Namorientation
タグ : / 解いたユーザー数 123
作問者 :
Problem Statement
You are given a connected simple undirected graph with $N$ vertices and $N$ edges. The vertices are numbered $1, 2, \dots, N$, and the $i$-th edge connects vertices $A_i$ and $B_i$.
By assigning a direction to each edge of this graph, convert it into a directed graph in which every vertex has out-degree $1$. It can be shown that an answer always exists under the constraints of this problem.
Notes
In a directed graph, the out-degree of a vertex is the number of edges that start at that vertex.
The undirected edge connecting $x, y$ is denoted by $(x, y)$. The directed edge with start point $x$ and end point $y$ is denoted by $x \rightarrow y$, and the directed edge with end point $x$ and start point $y$ is denoted by $x \leftarrow y$.
In this problem, assigning a direction to each edge of the undirected graph means that, for every $i$, the undirected edge $(A_i, B_i)$ is removed and exactly $1$ of the directed edges $A_i \rightarrow B_i$ or $A_i \leftarrow B_i$ is added in its place.
Constraints
- All input values are integers.
- $3 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \lt B_i \leq N$
- The given graph is connected and simple.
Input
The input is given from standard input in the following format.
$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$
Output
Output $N$ lines. On the $i$-th line, output -> if you remove the undirected edge $(A_i, B_i)$ and add the directed edge $A_i \rightarrow B_i$, or <- if you add the directed edge $A_i \leftarrow B_i$.
If there are multiple answers, any of them will be accepted.
Sample
Sample 1
Input
5 1 2 2 3 3 4 1 4 4 5
Output
-> -> -> <- <-
When the directed edges are added in this way, every vertex has out-degree $1$.
Sample 2
Input
7 1 2 2 4 4 5 1 7 2 3 3 7 3 6
Output
<- <- <- -> <- <- <-
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。