O. Ребро, без которого нельзя

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

Классная задача M спрашивала «хотя бы в одно». Здесь вопрос двойственный, и ответ строится из тех же двух конструкций — чередующегося обхода и компонент сильной связности.

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

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