M. Ребро, которое может пригодиться

Дан двудольный граф. Для каждого ребра нужно сказать, входит ли оно хотя бы в одно максимальное паросочетание.

В первой строке $n$, $m$ и $e$ ($1 \le n, m \le 2000$, $0 \le e \le 10^5$) — размеры долей и количество рёбер. В следующих $e$ строках по два числа $u$ и $v$ — концы ребра в первой и второй доле. Кратных рёбер нет.

Выведите строку из $e$ символов: $i$-й символ равен 1, если $i$-е ребро входит хотя бы в одно максимальное паросочетание, и 0 иначе.