[ARC076E] Connected?

## 题目描述 すぬけ君在玩一种解密游戏。这个游戏在 $R×C$ 的长方形盘面上进行，这个长方形盘面上写着 $1$ 到 $N$ 的整数，每个整数都出现了刚好两次。写着整数 $i$ 的坐标为 $(x_{i,1},y_{i,1})$ 和 $(x_{i,2},y_{i,2})$ 。 すぬけ君的目的是，对于 $1$ 到 $N$ 的每个整数，在写着相同整数的坐标之间连接一条曲线。此时，曲线不能在长方形之外，也不能与其它曲线相交。 请判断すぬけ君是否能达成他的目的。 ## 数据范围 - $1 \leq R,C \leq 10^8$ - $1 \leq N \leq 10^5$ - $0 \leq x_{i,1},x_{i,2} \leq R(1 \leq i \leq N)$ - $0 \leq y_{i,1},y_{i,2} \leq C(1 \leq i \leq N)$ - 任意两点坐标相异。 - 输入全为整数。 ## 输入 输入按以下标准。 $$ R \space C \space N $$ $$ x_{1,1} \space y_{1,1} \space x_{1,2} \space y_{1,2} $$ $$ : $$ $$ x_{N,1} \space y_{N,1} \space x_{N,2} \space y_{N,2} $$ ## 输出 如果すぬけ君能够达到目的，输出`YES`，否则输出`NO`。 （样例及解释见原题面）

[problemUrl]: https://atcoder.jp/contests/arc076/tasks/arc076_c すぬけ君は、パズルゲームで遊んでいます。 このパズルゲームでは、$ R\ ×\ C $ の長方形の盤面に、$ 1 $ から $ N $ までの整数が $ 2 $ つずつ書かれています。 整数 $ i $ が書かれている座標は、$ (x_{i,1},y_{i,1}) $ と $ (x_{i,2},y_{i,2}) $ です。 すぬけ君の目的は、$ 1 $ から $ N $ までのすべての整数に対し、同じ整数の書かれている座標同士を曲線で結ぶことです。 このとき、曲線が長方形の外に出たり、互いに交わったりしてはいけません。 このようなことが可能かどうか判定してください。

入力は以下の形式で標準入力から与えられる。 > $ R $ $ C $ $ N $ $ x_{1,1} $ $ y_{1,1} $ $ x_{1,2} $ $ y_{1,2} $ : $ x_{N,1} $ $ y_{N,1} $ $ x_{N,2} $ $ y_{N,2} $

すぬけ君が目的を達成できるなら `YES` を、そうでないなら `NO` を出力せよ。

4 2 3
0 1 3 1
1 1 4 1
2 0 2 2

YES

2 2 4
0 0 2 2
2 0 0 1
0 2 1 2
1 1 2 1

NO

5 5 7
0 0 2 4
2 3 4 5
3 5 5 2
5 5 5 4
0 3 5 1
2 2 4 4
0 5 4 1

YES

1 1 2
0 0 1 1
1 0 0 1

NO

### 制約 - $ 1\ ≦\ R,C\ ≦\ 10^8 $ - $ 1\ ≦\ N\ ≦\ 10^5 $ - $ 0\ ≦\ x_{i,1},x_{i,2}\ ≦\ R(1\ ≦\ i\ ≦\ N) $ - $ 0\ ≦\ y_{i,1},y_{i,2}\ ≦\ C(1\ ≦\ i\ ≦\ N) $ - 与えられるどの $ 2 $ 点も異なる - 入力は全て整数である ### Sample Explanation 1 !\[\](https://atcoder.jp/img/arc076/hogehogehoge.png) 上図のように整数同士を結べば、目的を達成することができます。