Faits: A. Par ordonnance du 14 mai 2010, le Ministère public du canton de Fribourg a renvoyé Y._ devant le Tribunal pénal d'arrondissement de la Sarine pour de nombreux chefs de prévention, répartis en une vingtaine de volets (comprenant des infractions au détriment de 520 artistes de cabaret, des infractions économiques et des infractions diverses). Par jugement du 30 mars 2012, le Tribunal pénal a notamment acquitté Y._, dans le volet X._, de tentative de traite d'êtres humains, de tentative d'encouragement à la prostitution, de tentative de contrainte, d'appropriation illégitime et d'abus de confiance. Le tribunal l'a reconnu coupable d'encouragement à la prostitution (volet autres artistes), d'escroquerie par métier (volet escroquerie), de faux dans les titres et de délit contre la LAVS (volet décomptes salaires), d'infraction à la LIFD et à la LICD (volet détournement de l'impôt à la source), de délit contre la LAVS (volet détournement de cotisations sociales), de contravention à la LAVS (volet non-remise de comptabilité) et de délit contre la LEtr (volet emploi sans autorisation). Il l'a condamné à une peine privative de liberté de vingt-deux mois avec sursis durant deux ans et à 300 fr. d'amende. Le tribunal a prononcé une créance compensatrice de 30'000 francs. B. La partie plaignante X._ a formé appel contre ce jugement. Elle a conclu à sa réforme en ce sens que Y._ soit reconnu coupable d'abus de confiance, subsidiairement d'appropriation illégitime, de tentative de contrainte, de tentative de traite d'êtres humains, subsidiairement de tentative d'encouragement à la prostitution. Elle a requis l'allocation d'une indemnité pour tort moral de 10'000 francs. Le ministère public a déclaré former un appel joint. Dans le volet X._, il a conclu à ce que Y._ soit reconnu coupable de tentative de traite d'êtres humains, de tentative d'encouragement à la prostitution et d'abus de confiance. Le ministère public a également attaqué le jugement sur d'autres points concernant en particulier les acquittements dans les volets A._, B._ et autres artistes. Pour l'ensemble des points querellés, il a requis une condamnation à une peine privative de liberté de trente-six mois, dont vingt-quatre avec sursis durant cinq ans, à une peine pécuniaire de 180 jours-amende à 40 fr., avec sursis durant cinq ans et à une amende de 4'000 francs. Il a sollicité que la créance compensatrice soit portée à 200'000 francs. C. Par arrêt du 14 août 2013, la Cour d'appel pénal du Tribunal cantonal du canton de Fribourg a décidé d'entrer en matière sur l'appel de X._ et d'entrer partiellement en matière sur l'appel joint du ministère public. En bref, la cour a considéré qu'il y avait uniquement lieu d'entrer en matière sur l'appel joint en tant qu'il s'inscrivait dans le cadre du volet X._, mais non sur les autres volets dès lors que ceux-ci n'auraient pas pu être attaqués par la partie plaignante dans son appel principal pour se rapporter à des faits étrangers à celle-ci. D. Le Ministère public de l'Etat de Fribourg forme un recours en matière pénale au Tribunal fédéral contre cet arrêt, concluant à son annulation. X._ conclut à l'admission du recours et sollicite l'assistance judiciaire. Y._ conclut au rejet du recours et sollicite l'assistance judiciaire. E. Le Tribunal fédéral a rendu son jugement en séance publique.