일방통행 보도
시간 제한5초메모리 제한256 MB
연결된 무방향 그래프가 주어질 때, 혼합 그래프의 강한 연결성을 유지하면서 양방향으로 남는 간선 수가 최소가 되도록 각 간선의 방향을 정한다.
문제
워털루의 일반적인 보도는 폭이 1.5미터이다. 반대 방향으로 걷는 두 사람은 2미터의 물리적 간격을 유지한 채 서로 지나칠 수 없다. 많은 도시는 한 방향으로만 사용하는 일방통행 보도를 지정해 왔다. 보통 반대 방향으로 걸을 수 있게 해 주는 다른 보도가 있다. 도시의 두 장소를 잇는 경로가 하나뿐이라서 이것이 불가능한 경우도 있다. 이런 경우 일부 도시는 보행 공간을 넓히기 위해 차도 일부를 차량에 대해 폐쇄한다. 이는 비용이 많이 들고 운전자를 화나게 하므로, 도시는 반드시 필요한 곳에서만 이렇게 한다.
입력
입력의 첫 줄에는 도시의 장소 수와 보도 수를 나타내는 두 정수 N, M이 주어진다. 0 ≤ N, M ≤ 200, 000이다. 모든 장소에서 다른 모든 장소로 가는 경로가 존재한다. 다음 M개의 줄은 각각 보도를 설명하며, 보도가 연결하는 두 장소를 나타내는 두 정수 A, B가 주어진다. 1 ≤ A, B ≤ N이다.
출력
보도마다 한 줄씩, 입력에 나열된 보도와 같은 순서로 총 M줄을 출력한다. 각 줄에는 보도를 장소 A에서 B 방향의 일방통행으로 만들면 >, 반대 방향의 일방통행으로 만들면 <, 양방향으로 유지하려면 보도를 넓혀야 하면 =를 출력한다. 넓혀야 하는 보도의 수를 최소화해야 한다. 넓혀야 하는 보도의 수를 최소화하는 해가 여러 개라면 그중 아무거나 출력해도 된다.