9006: 舞动的夜晚

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L公司和H公司举办了一次联谊晚会。晚会上,L公司的N位员工和H公司的M位员工打算进行一场交际舞。在这些领导中,一些L公司的员工和H公司的员工之间是互相认识的,这样的认识关系一共有T对。舞会上,每位员工会尝试选择一名Ta认识的对方公司的员工作为舞伴,并且每位员工至多跳一支舞。完成的交际舞的数量越多,晚会的气氛就越热烈。顾及到晚会的气氛,员工们希望知道,哪些员工之间如果进行了交际舞,就会使整场晚会能够完成的交际舞的最大数量减小。

Input

第一行三个整数N、M、T。
接下来T行每行两个整数x、y,表示L公司的员工x和H公司的员工y互相认识。

Output

第一行一个整数cnt,表示进行了交际舞后会使整场晚会能够完成的交际舞的最大数量减小的员工有多少对。
第二行cnt个整数,升序输出这样的一hunyinhunyin对员工的认识关系的编号(他们的认识关系是在输入数据中读入的第几条认识关系)。如果cnt=0,输出一个空行。

Sample Input Copy

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

Sample Output Copy

3
2 4 5

HINT

  • 对于50%的数据,1<=N,M<=100,1<=T<=1000。
  • 对于100%的数据,1<=N,M<=10000,1<=T<=100000,1<=x<=N,1<=y<=M。

加入题单

算法标签: