라우팅

베드로 팬은 앞으로의 직업을 정하는 데 도움을 받으려고 진로 상담을 받았다. 그러나 그는 어른이 되고 싶지 않아서 도망쳐 네버랜드에 숨었다.

네버랜드에는 서쪽에서 동쪽으로 흐르는 강이 두 개 있다. 첫 번째 강변에는 $a$개의 도시가 있고, 강이 흐르는 방향을 따라 $1$부터 $a$까지 번호가 붙어 있다. 두 번째 강에도 같은 방식으로 $1$부터 $b$까지 번호가 붙은 도시 $b$개가 있다. 강을 따라 내려갈 때, 두 도시가 같은 강에 있고 $i < j$이면 도시 $i$에서 도시 $j$로 갈 수 있다.

시민들은 일방향 항공편 $m$개를 만들 계획이다. $i$번째 항공편은 첫 번째 강의 도시 $x_i$와 두 번째 강의 도시 $y_i$를 잇는데, 방향은 아직 정하지 않았다. 시민들은 도시들이 최대한 서로 연결되기를 바란다. 그때 베드로 팬은 항공편의 방향을 정하는 일을 직업으로 삼고 싶어졌다.

두 도시는 서로에게서 상대 도시로 갈 수 있으면 연결되어 있다고 한다. 이동할 때는 항공편과 강을 모두 사용할 수 있다. 베드로 팬은 연결된 도시 쌍이 하나도 없는 도시 집합 중 가장 큰 것의 크기가 최소가 되도록 항공편의 방향을 정하려고 한다. 방향을 정하고 그 집합의 크기를 구하라.

첫 줄에 양의 정수 $a$, $b$, $m$($1 \le a, b, m \le 200\,000$)이 주어진다. 각각 첫 번째 강의 도시 수, 두 번째 강의 도시 수, 항공편 수이다.

다음 $m$개의 줄 중 $i$번째 줄에는 양의 정수 $x_i$와 $y_i$($1 \le x_i \le a$, $1 \le y_i \le b$)가 주어진다. 이는 첫 번째 강의 도시 $x_i$와 두 번째 강의 도시 $y_i$를 잇는 항공편이다. 같은 도시 쌍이 두 번 이상 주어지지 않는다.

첫 줄에 연결된 도시 쌍이 없는 도시 집합 중 가장 큰 것의 크기의 최솟값을 출력한다.

둘째 줄에는 0 또는 1로 이루어진 문자들을 공백으로 구분해 출력한다. 0은 항공편이 첫 번째 강에서 출발해 두 번째 강에 도착한다는 뜻이고, 1은 그 반대이다. 답이 여러 개이면 아무거나 출력해도 된다.

첫 번째 예제에서 항공편은 출력된 대로 방향이 정해진다. 어느 도시에서 출발해도 다른 모든 도시에 도달할 수 있다. 따라서 연결되지 않은 도시들의 최대 집합은 원소가 하나뿐인 집합이다. 예를 들어 첫 번째 강의 도시 5에서 출발해 첫 번째 강의 도시 1에 도달할 수 있다.

5 (I) → 3 (II) → 2 (I) → 3 (I) → 1 (II) → 2 (II) → 1 (I)