+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- منظور از یک **«گراف ساده»** $G$ یک ساختار دوتایی $(V, E)$ است. که به $V$ **«مجموعه‌ی راس‌ها»** و به $E$ **«مجموعه‌ی یال‌ها»**ی $G$ می‌گویند. اگر مجموعه‌ی راس‌های $G$ یا همان $V$ را یک مجموعه‌ی $n$ عضوی مثل $\{ v_1, v_2, \dots, v_n \}$ در نظر بگیرید. مجموعه $E$ یک مجموعه شامل تعدادی زیرمجموعه‌ی دو عضوی $V$ است. برای مثال اگر $V = \{1, 2, 3\}$ باشد، مجموعه $E$ می‌تواند $E = \{\{1, 2\}, \{1, 3\}\}$ باشد. از شما می‌خواهیم برنامه‌ای بنویسید که با دریافت $n$، بررسی کند که مجموعه $E$ حداکثر چند عضو دارد. به عبارت دیگر بررسی کنید یک گراف $n$ راسی، حداکثر چند یال دارد. # ورودی در تنها سطر ورودی، عدد صحیح و مثبت $n$ آمده است. $$1 \leq n \leq 10^9$$ # خروجی در تنها سطر خروجی یک عدد صحیح، که نشان‌دهنده‌ی حداکثر تعداد اعضای $E$ است، چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` 0 ``` اگر مجموعه $V = \{v_1\}$ باشد، زیرمجموعه‌ای دو عضوی ندارد. پس $$E = \emptyset$$ است. پس حداکثر تعداد عضو $E$ برابر ۰ است. ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` 1 ``` اگر $V = \{v_1, v_2\}$ باشد، تنها زیرمجموعه‌ی دو عضوی $V$ همان $\{ v_1, v_2 \}$ است پس، $$E = \{ \{v_1, v_2\}\}$$ حداکثر تعداد یال را دارد، پس حداکثر تعداد عضو $E$ برابر ۱ است. ## ورودی نمونه ۳ ``` 3 ``` ## خروجی نمونه ۳ ``` 3 ``` اگر $V = \{v_1, v_2, v_3\}$ باشد، ۳ زیرمجموعه‌ی دو عضوی $V$ عبارت است از $\{ v_1, v_2 \}$، $\{v_1, v_3, \}$ و $\{v_2, v_3\}$ است پس، $$E = \{ \{v_1, v_2\}, \{v_1, v_3\}, \{v_2, v_3\}\}$$ حداکثر تعداد یال را دارد، پس حداکثر تعداد عضو $E$ برابر ۳ است. ## ورودی نمونه ۴ ``` 4 ``` ## خروجی نمونه ۴ ``` 6 ``` اگر $V = \{v_1, v_2, v_3, v_4\}$ باشد، ۶ زیرمجموعه‌ی دو عضوی $V$ عبارت است از $\{ v_1, v_2 \}$، $\{v_1, v_3, \}$، $\{v_1, v_4\}$، $\{v_2, v_3\}$، $\{v_2, v_4\}$ و $\{v_3, v_4\}$ است پس، $$E = \{ \{v_1, v_2\}, \{v_1, v_3\}, \{v_1, v_4\}, \{v_2, v_3\}, \{v_2, v_4\}, \{v_3, v_4\}\}$$ حداکثر تعداد یال را دارد، پس حداکثر تعداد عضو $E$ برابر ‌۶ است.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فرض کنید $G$ یک گراف $n$ راسی و $m$ یالی با مجموعه راس‌های $\{v_1, v_2, \dots, v_n\}$ باشد. منظور از ماتریس مجاورت $G$ که معمولا آن را با $A$ نشان می‌دهند، یک ماتریس $n \times n$ است که درایه سطر $i$ام ستون $j$ام آن برابر ۱ است اگر و تنها اگر یال $\{v_i, u_j\}$ در $E$ موجود باشد. گراف $G$ به شما داده می‌شود و از شما می‌خواهیم ماتریس مجاورت $G$ را چاپ کنید. # ورودی در سطر اول ورودی دو عدد صحیح $n$ و $m$ که با یک فاصله از هم جدا شده‌اند آمده است که به ترتیب نشان‌دهنده‌ی تعداد راس‌ها و یال‌های گراف $G$ است. $$1 \leq n \leq 1000$$ $$0 \leq m \leq \frac{n(n - 1)}{2}$$ در $m$ سطر بعدی دو عدد $u_i$ و $v_i$ که با یک فاصله از هم جدا شده‌اند آمده است که نشان‌دهنده‌ی وجود یال $u_i v_i$ در گراف $G$ است. $$1 \leq u_i \neq v_i \leq n$$ تضمین می‌شود که هر یال موجود در $G$ دقیقا یکبار ورودی داده شود. # خروجی خروجی شامل $n$ سطر است که در هر سطر آن $n$ عدد صحیح بدون فاصله است. عدد نوشته شده در سطر $i$ام ستون $j$ام نشان‌دهنده‌ی درایه $a_{i, j}$ در ماتریس $A$ است. # مثال‌ها ## ورودی نمونه ۱ ``` 3 2 1 2 1 3 ``` ## خروجی نمونه ۱ ``` 011 100 100 ``` ## ورودی نمونه ۲ ``` 5 4 2 3 3 5 5 2 1 4 ``` ## خروجی نمونه ۲ ``` 00010 00101 01001 10000 01100 ``` ## ورودی نمونه ۳ ``` 1 0 ``` ## خروجی نمونه ۳ ``` 0 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فرض کنید $G$ یک گراف ساده $n$ راسی $m$ یالی است که راس‌های آن از $1$ تا $n$ شماره گذاری شده است. منظور از گراف مکمل $G$، که با $G^c$ نشان می‌دهیم. گرافی‌است با همان $n$ راس ولی یال‌های آن همه یال‌هایی است که در $G$ نیامده است. از شما $q$ پرسش داریم. در هر پرسش دو راس $u$ و $v$ به شما داده می‌شود و از شما می‌پرسیم که آیا یال $\{ u, v \}$ در گراف $G^c$ وجود دارد یا نه. # ورودی در سطر اول ورودی دو عدد صحیح $n$ و $m$ که با یک فاصله از هم جدا شده‌اند آمده است که به ترتیب نشان‌دهنده‌ی تعداد راس‌ها و یال‌های گراف $G$ است. $$1 \leq n \leq 100 \, 000$$ $$0 \leq m \leq \min\{\frac{n(n - 1)}{2}, 100 \, 000 \}$$ در $m$ سطر بعدی در هر سطر دو عدد $u_i$ و $v_i$ که با یک فاصله از هم جدا شده‌اند آمده است که نشان‌دهنده‌ی وجود یال $u_i v_i$ در گراف $G$ است. $$1 \leq u_i \neq v_i \leq n$$ تضمین می‌شود گراف داده شده ساده است. یعنی بین هر دو راس حداکثر یک یال آمده است. در سطر بعدی عدد صحیح و مثبت $q$ آمده است. $$1 \leq q \leq 100 \, 000$$ در $q$ سطر بعدی در هر سطر دو عدد $u_j$ و $v_j$ که با یک فاصله از هم جدا شده‌اند آمده است و نشان‌دهنده‌ی این پرسش است که آیا یال $\{ u_j, v_j \}$ در $G^c$ وجود دارد یا نه. $$1 \leq u_j \neq v_j \leq n$$ # خروجی خروجی شامل $q$ سطر است و در سطر $j$ام در صورتی که یال $\{ u_j, v_j \}$ در $G^c$ وجود دارد رشته `YES` و در غیراین صورت رشته `NO` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 1 2 2 3 3 2 1 2 3 1 3 ``` ## خروجی نمونه ۱ ``` NO NO YES ``` ## ورودی نمونه ۲ ``` 4 3 2 4 4 3 2 3 6 1 2 1 3 1 4 2 3 2 4 3 4 ``` ## خروجی نمونه ۲ ``` YES YES YES NO NO NO ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فرض کنید $G$ یک گراف ساده $n$ راسی $m$ یالی است که راس‌های آن از $1$ تا $n$ شماره گذاری شده است. به یک گراف «اویلری» می‌گوییم اگر **«گذری»** داشته باشد که هر یال $G$، دقیقا یکبار در آن آمده باشد. منظور از یک گذر، دنباله‌ای از یال‌ها مثل $e_1, e_2, \dots, e_k$ است که به ازای هر $2 \leq i \leq k$ داشته باشیم $e_{i - 1} \cap e_i \neq \emptyset$. یک گراف به شما داده می‌شود، و از شما می‌خواهیم بررسی کنید آیا این گراف اویلری است یا نه. # ورودی در سطر اول ورودی دو عدد صحیح $n$ و $m$ که با یک فاصله از هم جدا شده‌اند آمده است که به ترتیب نشان‌دهنده‌ی تعداد راس‌ها و یال‌های گراف $G$ است. $$1 \leq n \leq 100 \, 000$$ $$0 \leq m \leq \min\{\frac{n(n - 1)}{2},100 \, 000\}$$ در $m$ سطر بعدی دو عدد $u_i$ و $v_i$ که با یک فاصله از هم جدا شده‌اند آمده است که نشان‌دهنده‌ی وجود یال $u_i v_i$ در گراف $G$ است. $$1 \leq u_i \neq v_i \leq n$$ تضمین می‌شود گراف داده شده ساده است. یعنی بین هر دو راس حداکثر یک یال آمده است. # خروجی در تنها سطر خروجی در صورت اویلری بودن گراف $G$ رشته `YES` و در غیر این‌ صورت رشته `NO` چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 3 1 2 1 3 2 3 ``` ## خروجی نمونه ۱ ``` YES ``` بله، چون دنباله زیر وجود دارد: $$\{1, 2\}, \{2, 3\}, \{1, 3\}$$ ## ورودی نمونه ۲ ``` 4 2 1 2 3 4 ``` ## خروجی نمونه ۲ ``` NO ``` خیر، چون هر این گراف تنها دو یال دارد که هیچ اشتراکی ندارند. پس نمی‌توان دنباله‌ای ساخت که هر دو یال در آن حضور داشته باشند و هر دو یال متوالی اشتراکی ناتهی داشته باشند. ## ورودی نمونه ۳ ``` 5 5 1 2 2 3 3 4 4 5 5 3 ``` ## خروجی نمونه ۳ ``` YES ``` بله، چون دنباله زیر وجود دارد: $$\{1, 2\} \{2, 3\}, \{3, 4\}, \{4, 5\}, \{3, 5\}$$

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فرض کنید $G$ یک گراف ساده $n$ راسی $m$ یالی است که راس‌های آن از $1$ تا $n$ شماره گذاری شده است. به یک گراف هملیتونی می‌گوییم اگر دوری داشته باشد که از **هر راس دقیقا یکبار** عبور کند. یک گراف به شما داده می‌شود که همیلتونی است، از شما می‌خواهیم یکی از دورهای همیلتونی آن را پیدا کنید. # ورودی در سطر اول ورودی دو عدد صحیح $n$ و $m$ که با یک فاصله از هم جدا شده‌اند آمده است که به ترتیب نشان‌دهنده‌ی تعداد راس‌ها و یال‌های گراف $G$ است. $$3 \leq n \leq 100$$ $$n \leq m \leq \frac{n(n - 1)}{2}$$ در $m$ سطر بعدی دو عدد $u_i$ و $v_i$ که با یک فاصله از هم جدا شده‌اند آمده است که نشان‌دهنده‌ی وجود یال $u_i v_i$ در گراف $G$ است. $$1 \leq u_i \neq v_i \leq n$$ تضمین می‌شود گراف داده شده ساده است. یعنی بین هر دو راس حداکثر یک یال آمده است. # خروجی در تنها سطر خروجی یکی از جایگشت‌های اعداد $1$ تا $n$ مثل $v_1, v_2, \dots, v_n$ را چاپ کنید به طوری که تشکیل یک دور همیلتونی بدهد؛ یعنی $v_i$ و $v_{i \% n + 1}$ برای هر $i$ از $1$ تا $n$ به یکدیگر یال داشته‌ باشند. # مثال‌ها ## ورودی نمونه ۱ ``` 5 5 1 2 4 3 4 5 5 1 3 2 ``` ## خروجی نمونه ۱ ``` 3 4 5 1 2 ``` ## ورودی نمونه ۲ ``` 3 3 1 2 2 3 3 1 ``` ## خروجی نمونه ۲ ``` 1 2 3 ```