+ محدودیت زمان: ۱ ثانیه + **محدودیت حافظه: ۳۲ مگابایت** ---------- چند صباحی است که مجید به دنبال کار در شرکت‌های برنامه‌نویسی می‌گردد، اما شرکت‌های برنامه‌نویسی به دلایل نامعلومی او را رد می‌کنند . امروز مجید تصمیم گرفته که شانس خود را برای شرکت سحاب امتحان کند، بدین منظور مجید رزومه خود را برای شرکت سحاب می‌فرستد. بعد از بررسی رزومه مجید، شرکت سحاب متوجه می‌شود که این مجید همان مجید مشهور است و در نتیجه می‌خواهند که او را برای کار در شرکت نپذیرند، اما از آنجا که مسئولین استخدام شرکت سحاب انسان‌های مهربانی هستند، یک شانس به مجید می‌دهند و به اون می‌گویند در صورتی استخدام می‌شود که بتواند از یک مسیری به شرکت سحاب برسد و در این مسیر از هر شهری حداکثر یک بار عبور کند! کشوری که مجید در آن زندگی می‌کند شامل $n$ شهر و $m$ جاده‌ی دو طرفه است، که شهرها از ۰ تا $n-1$ شماره‌گذاری شده‌اند ولی جاده‌های این کشور به طرز عجیبی طراحی شده‌اند. جاده‌ها بطور کاملاً تصادفی کشیده شده‌اند! برای هرچه بیشتر تصادفی شدن این جاده‌کشی، از الگوریتم *KISS* (مخفف *Keep It Simple Stupid*) برای ساخت اعداد تصادفی و کشیدن جاده‌ها استفاده شده‌ است. کد این الگوریتم در زبان ++C به شکل زیر است. (مقادیر اولیه‌ی متغیرهای $x$ و $y$ و $z$ و $c$ در ورودی به شما داده ‌می‌شود.) ```c++ unsigned long long x, y, z, c; unsigned long long uint32(unsigned long long i) { return i & 0xFFFFFFFF; } unsigned long long kiss() { x = uint32( 69069 * x + 12345 ); y ^= uint32(y << 13); y ^= uint32(y >> 17); y ^= uint32(y << 5); unsigned long long t = 698769069 * z + c; c = uint32(t >> 32); z = uint32(t); return uint32(x + y + z); } ``` سپس مسئولین بین شهر‌ها به صورت زیر جاده احداث کرده‌اند. (تابع `build_road_between` بین دو شهر یک جاده دوطرفه قرار می‌دهد.) ```c++ for (int i = 0; i < m; i++) { int u = kiss() % n; int v = kiss() % n; build_road_between(u , v); } ``` **دقت کنید** که ممکن است بین ۲ شهر بیش از یک جاده احداث شود و یا ممکن است از یک شهر به خودش جاده‌ای وجود داشته باشد. با توجه به اینکه مجید به دلایل نامعلومی نمی‌تواند مسیر رسیدن به سحاب را پیدا کند، از شما کمک خواسته تا بلکه شما بتوانید به او برای رسیدن به این شرکت و این شغل کمک کنید. **(به محدودیت حافظه و ورودی‌های این سوال دقت کنید، حافظه به گونه‌ای محدود شده که نتوان اطلاعات کل جاده ها را نگه داشت.)** # ورودی در خط اول ورودی $n$ و $m$ که به ترتیب تعداد شهر ها و تعداد جاده‌ها است آمده. در خط بعدی به ترتیب ۴ عدد $x$ و $y$ و $z$ و $c$ آمده‌است. و در خط آخر ابتدا شماره شهری که مجید در آن است($start$) و سپس شماره شهری که شرکت سحاب در آن واقع شده($end$)، آمده است. $$2 \le n \le 100\ 000$$ $$0 \le m \le 10\ 000\ 000$$ $$0 \le x, y, z, c \le 1\ 000\ 000\ 000$$ $$0 \le start , end \le n-1$$ $$start \neq end$$ # خروجی در خط اول خروجی تعداد جاده ها برای رسیدن از شهر مجید به شهر شرکت سحاب را چاپ کنید و در خط بعدی به ترتیب شماره شهرهایی که مجید در این مسیر از آن‌ها می‌گذرد(همراه با شهر مبدا و مقصد) را چاپ کنید.(در صورتی که چندین مسیر مطلوب وجود داشت یکی از آن‌ها را به دلخواه چاپ کنید.) **مسیری که چاپ می‌کنید نباید شامل هیچ‌گونه دوری باشد، همچنین طول مسیری که به عنوان جواب چاپ می‌کنید باید کمتر از $n$ باشد.(تضمین می‌شود در صورت وجود جواب، مسیری وجود دارد که طول آن کمتر از $n$ باشد.)** در صورتی که مسیری برای رسیدن به شرکت سحاب وجود نداشت ```-1``` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 4 2 3 2 2 1 3 ``` ## خروجی نمونه ۱ ``` 1 1 3 ``` **توضیح نمونه‌ی ۱:** با توجه به الگوریتم *KISS* جاده‌ی‌ اول بین شهرهای ۲و۳، جاده‌ی دوم بین شهرهای ۰و۳، جاده‌ی سوم بین شهرهای ۱و۳ و جاده‌ی چهارم بین شهرهای ۱و۲ کشیده می‌شود. در نتیجه شکل نهایی جاده ها به صورت زیر خواهد بود.  ## ورودی نمونه ۲ ``` 100 99 8 97 46 1 90 77 ``` ## خروجی نمونه ۲ ``` 17 90 55 19 24 54 91 35 0 49 87 38 72 84 80 18 32 75 77 ```

حل سؤال در بانک سؤالات