1024 - dance party
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 733
Solved: 261
- Description
- You are organizing a dance party. The party will be attended by n boys and n girls. There will be several rounds of dancing.
In each round, you divide the guests into n dancing pairs. Each guest must be in exactly one pair, and each pair must contain one boy and one girl. Each boy must dance with a different girl in every round. Some boys and girls like each other and some do not. During the party, each boy agrees to dance with at most k girls he doesn't like. Similarly, each girl agrees to dance with at most k boys she doesn't like.
You are given the each pairs of boys and girls who agree to dance with each other .Find out the maximum number of rounds you can organize.
- Input
- The first line contains a integer t,which means there are t cases followed.
For each case,the first line contain three integer n,m,k ,which means there are n boys and n girls attending the party and m pairs of boys and girls who agree to dance with each other,and each boy or girl agrees to dance with at most k girls or boys he or she doesn't like.At last ,there are m lines with two integers a,b which means boy a and girl b agree to dance with each other.
（0<n<=100,0<m<=n*n,0<k<100,0<a,b<=n）
- Output
- The output cotains only one integer which means the maximum number of rounds you can organize.
- sample input
-
2 2 4 0 1 1 2 2 2 1 1 2 3 7 0 1 1 1 2 1 3 2 1 2 2 3 1 3 3
- sample output
-
2 2
- hint
- source
- lshmouse