問題一覧 > 通常問題

No.2301 Namorientation

レベル : / AI推定難易度 : 1025 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 123
作問者 : Shirotsume / テスター : 👑 AngrySadEight ygussany
お気に入りにしたユーザー ProblemId : 9357 / 自分の提出
問題文最終更新日: 2023-05-09 00:21:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 388 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。