{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n h1 { font-size: 1.2em; }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"En la Universidad de Chipre, hay $n$ estudiantes y $m$ ramos en los que se necesita un auxiliar. Un estudiante solo puede ser auxiliar de máximo un ramo, y un ramo puede tener como máximo un solo auxiliar.\n\nEl problema es que un estudiante no puede ser auxiliar de cualquier ramo, ya que quizás no le interesa, o no tiene el conocimiento. Así que hay $k$ emparejamientos factibles de estudiante-ramo.\n\nEres el jefe docente del DCC de la UChipre, y tu tarea es maximizar la cantidad de ramos que tienen auxiliares.\n"}},{"title":"Entrada","value":{"format":"MD","content":"La primera línea contiene los enteros $n$, $m$ y $k$ ($1 \\leq n, m \\leq 500$, $1 \\leq k \\leq 1000$): la cantidad de estudiantes, ramos y potenciales emparejamientos. Los estudiantes se enumeran $1, 2, \\dots, n$ y los ramos $1, 2, \\dots, m$\n\nDespués de eso, hay $k$ líneas indicando los emparejamientos posibles. Cada línea tiene dos enteros $a$ y $b$ ($1 \\leq a \\leq n$, $1 \\leq b \\leq m$), indicando que el estudiante $a$ podría ser auxiliar del ramo $b$."}},{"title":"Salida","value":{"format":"MD","content":"Imprime un entero $x$ indicando la máxima cantidad de emparejamientos. Después, imprime $x$ líneas indicando cada emparejamiento. Puedes imprimir cualquier solución válida (que maximice $x$)."}},{"title":"Ejemplo","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSalida\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2 4\n1 1\n1 2\n2 1\n3 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1 2\n3 1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Nota","value":{"format":"MD","content":"Esta solución maximiza la cantidad de estudiantes que son auxiliares, o la cantidad de ramos que tienen auxiliar (son equivalentes porque se relacionan uno a uno)."}}]}