All submissions for this problem are available.
21st century is the internet century. Most part of our life revolves around the internet which keeps people so busy with their work, that they don’t have enough time to find suitable dates for themselves. To help people with this, there is a startup which takes the preferences of people and arranges suitable dates for them.
To avail this service, girls and boys need to register on their website. Girls give their preferences for their dates among the boys registered on the site. The site then randomly generates pairs of a boy and a girl and sets them on a date. The website chooses a match such that everyone has a date while ensuring that every girl has exactly one boy as her date and every boy has exactly one girl as his date.
There may be a few girl-boy pairs who may never be matched together by the startup while trying to find exactly one match for everybody. You are asked to output all such girl-boy pairs.
The first line contains a single integer T, the number of test cases.
The first line of each test case contains three space separated integers, N1 N2 M where
- N1: The number of girls
- N2: The number of boys
- M: The total number of preferences the girls give
The next M lines are such that each contains two space separated integers A B which means that the girl A would like to date boy B.
For each test case, in the first line print P the number of girl-boy pairs who will never be able to date, followed by all the pairs, each in one line. Each pair will be output as two space separated integers, i j, where the ith girl would never be able to date the jth boy. All the pairs must be reported in the lexicographic order; i.e. report pair i j before k l, when i < k or when i = k and j < l.
- 1 ≤ T ≤ 10
- 1 ≤ N1, N2 ≤ 500
- 1 ≤ M ≤ 250000
- 1 ≤ A ≤ N1
- 1 ≤ B ≤ N2
Input: 2 1 1 1 1 1 3 3 4 1 1 1 2 2 3 3 3 Output: 0 4 1 1 1 2 2 3 3 3
|Time Limit:||0.208835 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions