P4610 [COI 2012] KAMPANJA

临近选举，总统要在城市 $1$ 和城市 $2$ 举行演讲。他乘汽车完成巡回演讲，从 $1$ 出发，途中要经过城市 $2$，最后必须回到城市 $1$。特勤局对总统要经过的所有城市监控。为了使得费用最小，必须使得监控的城市最少。求最少要监控的城市。

一共有 $N$ 个城市和 $M$ 条有向边。满足 $2 \le N \le 100,2 \le M \le 200$。 我们要求出从 $1$ 号城市出发途中要经过 $2$ 城市，最后要回到 $1$ 城市的路线中最少要经过的点的数目。测试数据保证一定存在解。

第一行包含 $2$ 个整数 $N,M$。$N$ 表示城市的数目，$M$ 表示有向边的数目。 接下来 $M$ 行，每行两个数 $A,B$，表示从 $A$ 到 $B$ 有一条有向边。

最少要监控的城市的数量。

对于 $100\%$ 的数据，满足 $2 \le N \le 100,2 \le M \le 200$。 本题数据加强by Imagine