410003 - 过山车

一群人去游乐场玩过山车,但是过山车的每一排只有两个座位,而且必须是一男一女做同伴。现给出所有男生女生搭配的信息,问最多有多少对组合可以坐过山车。

Input

有多组数据,每组数据第一行是三个整数K,M和N,表示可能的组合数,男生数和女生数(0<K≤1 000,1≤N和M≤500)。 接下来的K行,每行有两个数,分别表示男生Ai愿意和女生Bj做同伴。最后一个0结束输入。

Output

对于每组数据,输出一个整数,表示可以坐上过山车的最多组合数。

Examples

Input

6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0

Output

3
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题