+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- منظور از یک **«گراف ساده»** $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$ یک ساختار دوتایی $(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$ است، چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

اگر مجموعه $V = \{v_1\}$ باشد، زیرمجموعه‌ای دو عضوی ندارد. پس $E = \emptyset$ است. پس حداکثر تعداد عضو $E$ برابر ۰ است.

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

اگر $V = \{v_1, v_2\}$ باشد، تنها زیرمجموعه‌ی دو عضوی $V$ همان $\{ v_1, v_2 \}$ است پس، $E = \{ \{v_1, v_2\}\}$ حداکثر تعداد یال را دارد، پس حداکثر تعداد عضو $E$ برابر ۱ است.

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

اگر $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$ برابر ۳ است.

ورودی نمونه ۴🔗

خروجی نمونه ۴🔗

اگر $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

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

1 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$ ، که با $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 را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

NO
NO
YES

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

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$ شماره گذاری شده است.

به یک گراف «اویلری» می‌گوییم اگر «گذری» داشته باشد که هر یال $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 چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

YES

بله، چون دنباله زیر وجود دارد: $\{1, 2\}, \{2, 3\}, \{1, 3\}$

ورودی نمونه ۲🔗

4 2
1 2
3 4

خروجی نمونه ۲🔗

NO

خیر، چون هر این گراف تنها دو یال دارد که هیچ اشتراکی ندارند. پس نمی‌توان دنباله‌ای ساخت که هر دو یال در آن حضور داشته باشند و هر دو یال متوالی اشتراکی ناتهی داشته باشند.

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

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$ به یکدیگر یال داشته‌ باشند.

مثال‌ها🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

3 4 5 1 2

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

1 2 3