P3090 [USACO13NOV] Empty Stalls G

Farmer John's new barn consists of a huge circle of N stalls (2

\* Line 1: Two space-separated integers: N and K. \* Lines 2..1+K: Each line contains integers X Y A B, interpreted as above. The total number of cows specified by all these lines will be at most N-1. Cows can be added to the same stall by several of these lines.

\* Line 1: The minimum index of an unoccupied stall.

There are 10 stalls in the barn, numbered 0..9. The second line of input states that 3 cows prefer stall (2\*1+4) mod 10 = 6, and 3 cows prefer stall (2\*2+4) mod 10 = 8. The third line states that 2 cows prefer stall (0\*1+1) mod 10 = 1. Line four specifies that 1 cow prefers stall (1\*1+7) mod 10 = 8 (so a total of 4 cows prefer this stall). All stalls will end up occupied except stall 5.