SP25684 JOLLYKINGDOM - Jolly Kingdom

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 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 **Output** Print H lines. Each line contains 1 number represents the answer to the king's question. **Sample Tests** Input ```

4 4 9
1 1
1 2
1 3
2 1
4 1
3 4
3 3
4 3
4 4
```
  Output  ```
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 $ ^{6} $ (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:  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](https://id.linkedin.com/in/sandy-karunia-150097a8 "Sandy Karunia") - Developer of [Jollybee Online Judge](https://jollybeeoj.com/)
- [Alvin Setiadi](https://id.linkedin.com/in/alvin-setiadi-512289aa "Alvin Setiadi") - Original problem author
                            

N/A

N/A