Jolly Kingdom is a kingdom which is famous for its troops' power. Jolly Kingdom has N swordsman troops and M archer troops where each troop has his/her own unique fighting style, different with others.

For the 10^th times, an evil witch with her monster troops tries to seize the throne of Jolly Kingdom. According to the information gathered from Jolly Kingdom's spies, the witch will attack everyday for H days. Each day, the witch will add 1 new monster into her monster troops. This makes enemy's troops become stronger every day.

Each monster owned by the witch is strong and almost unbeatable, only the X_i^th swordsman troop or the Y_i^th archer troop can beat the monster. After the monster has been defeated by Jolly Kingdom's troop, that monster will take a reset and attack again in the next day.

To protect Jolly Kingdom, every day all monsters have to be defeated, but the cost to send 1 troop is expensive, so the king wants to send minimum number of troops every day such that the sent troops will be able to defeat all monsters exist on that corresponding day.

The king asks you for your help, as a royal advisor, the number of troops the king has to send every day.

Input

First line consists of 3 integers: N, M, and H (1 ≤ N, M ≤ 1000; 1 ≤ H ≤ N*M) – the number of swordsman troops, archer troops, and days. Each of next H lines contains 2 integers: X_i and Y_i (1 ≤ X_i ≤ N; 1 ≤ Y_i ≤ M) – the weakness of i^th monster, i^th can be defeated by the X_i^th swordsman or Y_i^th archer.

There can't be 2 monsters with the exact same weakness (there won't be any monster i and j where X_i = X_j and Y_i = Y_j for all 1 ≤ i, j ≤ H and i ≠ j).

Output

Print H lines. Each line contains 1 number represents the answer to the king's question.

Sample Tests

4 4 9
1 1
1 2
1 3
2 1
4 1
3 4
3 3
4 3
4 4

1
1
1
2
2
3
3
4
4

Explanation for sample case

Notation: { swordsman troop number: monster number(s) defeated } { archer troop number: monster number(s) defeated }
1^st day: {1: 1} {}
2^nd day: {1: 1 2} {}
3^rd day: {1: 1 2 3} {}
4^th day: {1: 1 2 3} {1: 4}
5^th day: {1: 1 2 3} {1: 4 5}
6^th day: {1: 1 2 3; 3: 6} {1: 4 5}
7^th day: {1: 1 2 3; 3: 6 7} {1: 4 5}
8^th day: {1: 1 2 3; 3: 6 7; 4: 8} {1: 4 5}
9^th day: {1: 1 2 3; 3: 6 7; 4: 8 9} {1: 4 5}

Information

• The constraints above is not typo, N and M can be as large as 1000 (1 Thousand), so H can be as large as 10⁶ (1 Million). So this problem has 10× larger constraints than the original one.
• Warning: Large Input/Output files, each file I/O can be as large as 7.5 Megabytes (7.5 MB), cin or cout probably too slow for I/O, it's recommended to use scanf/printf (I've tested it).
• If you find this problem too hard, you can try this first: https://jollybeeoj.com/problem/view/199 original problem with smaller constraints.

Trivia

• The total size of file I/O in this problem is slightly more than 100 MB, took a while to generate, modify, and upload it. :)
• If the witch attack Jolly Kingdom everyday for 1 Million days that means the attack took more than 2500 years. :o
• If I count number of operation in the deepest loop of my algo on worst case input, it will be 671,163,499 operations.

Credit & Special thanks

• Sandy Karunia - Developer of Jollybee Online Judge
• Alvin Setiadi - Original problem author