After you've proven yourself in the Coliseum to the Grand Noah Queen, you'll be approached by Cerberus and Dullahan after you leave the throne room. Once you force them to stop talking over each other, talk to Dullahan and she'll ask for your help to resolve a situation in Yamatai Village.
- Head east from Grand Noah till you reach a tunnel entrance.
- Go through the tunnel to the other side where you'll find Yamatai Village.
- Enter the village and head north until you find the town hall. Talk to the elder and he'll tell you the four shrines are in disarray, and he needs your help.
- Leave the building and immediately head north to the four shrines.
- The first shrine is the Cat Shrine where the Nekomata in charge has gone missing. Talk to all the Nekomata there until you get one that gives a different response from "Nyaa." You'll know you found the right one when the party comments on it. Talk to the Shrine Priestess and she'll choose a different Nekomata to be the new leader. Cat Shrine complete.
- Next is the Fox Shrine. Simply enter the shrine area and talk to Nero, then enter the house, talk to Tamamo and you're done.
- The third shrine is the Tanuki shrine. Talk to the Kitsune there and she'll reveal she dared the Tanuki to enter Yamata no Orochi's cave and hasn't returned. Leave Yamatai Village and head north to the cave. You'll find two paths. If you want to recruit Shirohebi, take the left path. Jump across some stones, head down the rope, and enter a hidden cave behind the waterfall. Open all the chest inside to find a Cat Statue you need to recruit Shirohebi. Return to the first room and take the right path. There is another secret area behind the waterfall. Simply head west and you'll find the Tanuki cowering in a corner. Talk to her and you'll be warped back to the Tanuki shrine. Done.
- Go to the Snake Shrine and talk to Shirohebi's sister, the one with the blue flowers in her hair. Enter the building and watch a brief cutscene involving Neris and Shirohebi. Snake Shrine complete. Talk to her and give her the Cat Statuette from Yamatai Orochi if you want to recruit her.
- Return to the village elder and the quest will complete. The village elder will give you the Eastern Book of Secrets and Dullahan will officially join your party.
Once you head outside, you'll find four perverts who discuss their plans to leave town and see the world, and all it has to offer. Talk to them to begin their quest.